N=100;
H=[-34662020,-28293750,-27418573,-24190092,-20794529,-14537486,-7814580,-72690200,-64118299,-59309740,-56718145,-50345757,-45091324,-37434272,-96653924,-89456392,-81491839,-78863741,-79135048,-73836839,-72062965,-123748986,-123280620,-121232373,-112797847,-113324622,-109500164,-101933927,-154467292,-152495635,-148556079,-140868882,-132961636,-127137356,-125280587,-172771489,-172358035,-164670766,-160456841,-156152821,-154091957,-154125087,-188359811,-185244698,-182596900,-182124362,-177553218,-174672079,-173851490,-190243752,0,-954457,4864254,7918126,10655822,13280768,12884458,18975962,24060364,30818959,30027351,32607851,35054781,42425504,43612649,49816621,52936679,58611139,63245770,65181490,67013526,72708301,78907816,84198355,90158875,92662615,98650548,105778088,107148871,107274939,112606626,116141456,118542323,118064924,121995438,130184750,133075705,139151708,147296915,154537576,157768122,159150374,164291092,164984680,173348376,179079268,184127605,192147228,200726522,200360263];
X0=295736873;
M=1000;
S=[44,41,50,68,36,52,4,69,92,82,89,65,11,80,93,72,5,61,41,50,34,49,92,60,35,92,78,17,35,39,24,94,14,77,80,73,100,6,80,52,82,94,28,22,6,10,62,67,26,57,60,64,58,99,33,31,32,4,21,46,30,1,44,65,39,53,55,14,28,8,13,35,39,83,78,15,34,32,39,22,24,33,22,57,45,25,1,43,22,45,19,72,90,7,73,32,49,37,58,67,79,66,74,14,65,95,97,92,42,14,63,57,2,81,5,42,21,35,82,42,96,5,42,57,81,21,82,51,23,77,100,76,31,68,22,41,10,63,99,53,65,88,28,77,51,13,80,47,5,94,71,69,9,53,53,58,17,84,66,86,80,69,7,74,70,27,95,32,32,87,2,94,93,83,21,84,1,85,94,56,8,4,63,52,3,49,59,31,53,6,35,73,6,98,10,79,50,29,79,19,22,55,85,48,21,41,69,71,23,78,65,37,40,58,56,3,53,85,58,96,28,16,15,8,47,42,80,44,78,87,88,15,7,55,79,85,72,87,98,58,32,78,15,90,100,4,56,38,50,49,81,29,36,26,80,31,45,94,91,81,5,57,53,82,17,71,50,34,52,25,6,77,74,98,90,88,19,70,97,81,56,17,99,94,84,44,89,39,7,90,97,74,61,35,9,37,3,79,57,71,7,55,51,100,56,18,17,49,27,100,6,36,89,2,78,19,95,10,9,30,56,30,12,59,17,17,86,48,16,92,47,84,3,45,28,27,89,94,55,90,6,66,58,68,99,82,57,73,87,80,14,85,98,94,23,32,20,31,55,19,62,72,42,13,3,59,28,14,51,38,6,31,14,8,79,39,21,2,55,94,71,30,95,76,96,26,69,58,4,38,71,54,39,68,12,46,82,58,69,58,88,42,89,16,42,35,44,22,66,90,74,47,94,17,63,71,9,50,84,19,36,84,44,73,13,96,95,43,54,100,30,73,2,79,83,73,73,1,36,85,12,46,52,40,30,11,8,98,59,67,59,80,67,30,73,97,59,96,54,45,14,10,54,24,16,71,90,74,33,63,13,84,54,42,31,53,89,53,53,57,24,15,9,13,19,44,65,80,36,92,48,74,89,76,19,7,77,3,21,99,85,29,86,71,71,2,98,38,89,31,93,61,50,23,96,66,74,46,38,27,46,4,95,31,89,94,3,58,71,95,3,25,68,99,74,90,9,86,92,71,29,53,10,88,68,99,11,67,82,4,30,54,80,17,10,60,68,72,88,17,53,7,98,66,100,29,19,10,62,19,79,53,64,43,70,59,37,35,69,64,62,50,15,85,17,29,8,1,44,38,41,32,98,59,12,55,4,27,11,77,28,11,26,54,8,17,51,58,31,63,88,89,25,24,60,36,15,45,11,30,96,100,49,28,52,63,7,76,39,65,68,12,78,55,20,27,48,56,80,5,49,67,2,27,33,71,56,15,25,81,54,39,71,31,2,91,45,39,90,81,91,52,81,31,39,47,83,28,35,22,20,40,94,80,85,96,9,45,33,94,34,29,44,61,7,69,79,86,51,92,60,62,22,62,45,58,85,99,42,73,55,48,73,15,64,8,44,81,12,59,38,38,72,1,43,66,87,75,15,17,25,32,75,67,98,88,90,93,79,95,24,66,42,62,70,6,54,44,70,66,16,61,26,1,29,65,13,75,86,5,80,28,2,48,82,57,2,90,71,40,52,59,99,99,66,60,78,78,3,60,25,19,28,79,15,88,91,85,60,52,10,95,41,51,28,12,32,42,9,48,27,71,22,32,33,80,30,58,71,37,41,32,60,56,59,21,48,3,57,46,71,61,90,97,33,26,62,52,47,79,41,86,20,35,92,4,40,26,85,72,67,16,42,44,18,97,39,71,8,86,22,6,69,58,13,67,62,29,27,76,30,12,97,76,16,82,85,84,87,63,53,26,96,35,60,32,45,71,26,9,21,13,16,74,48,31,25,26,18,45,5,8,44,29,84,43,21,73,91,32,69,36,29,21,89,50,6,40,7,56,86,20,85,64,70,42,71,88,28,60,99,88,59,81,95,98,60,41,34,36,44,20,4,37,68,55,93,85,71,13,38,73,62,90,10,32,67,26,33,54,84,94,44,31,88,41,13,31,39,83,78,43,78,72,35,2,80,1,90,4,97,9,97,10,45,76,95,7,25,70,36,11,88,32,16,14,54,77,28,88,79,69,31,2,36,72,89,3,24,19,95,100,15,33,91,71,73,10,59,98];
X=[1000000000,318886702,292556791,1000000000,563176381,179934823,53804089,106559831,99653672,157109086,403655504,156670192,545055840,177525023,492762229,100989840,75104748,874486,986248702,2181150,498004627,106936181,1000000000,871121667,62168930,1000000000,1000000000,27680554,542299980,274172855,8526293,152819412,924808175,43113307,1000000000,12508550,110493693,129739130,13822977,1000000000,1000000000,601065710,159423515,171485454,690147581,196983429,211533538,1000000000,222136462,269608134,160549401,1000000000,33373187,91609333,472849228,238385648,87091955,82935278,295897001,15352413,314816991,272674032,26580084,180543140,22742369,127120240,140970044,807108887,602936484,90389579,186963516,1000000000,27830621,79013820,28165220,24565064,1000000000,281794529,322835295,68458876,2278739,874282722,13546745,219890359,293911854,1000000000,13100837,46909584,18698799,280269824,6004206,480593507,66104956,1000000000,1000000000,320838273,77867010,849573715,36741500,59639396,42674637,414040995,184960560,98952536,54042682,29908387,421120090,161812499,451977211,475817797,260041461,1904497,88765023,399748797,351469363,208793696,106041311,48745924,181986454,7842678,241094671,129507139,200406008,383017,354947481,381326418,1000000000,210200857,49390391,12989641,214871784,109161672,89215551,48001141,30720623,448573576,55393551,498843673,197426866,320589137,144740520,180014934,188379012,2463151,116137961,302772449,9370159,60229128,4056823,106223805,362232254,60617695,6807112,12671009,1000000000,193236719,136092348,262554457,15523698,755181280,164339787,1000000000,180808031,238581949,220904448,74072906,1000000000,142215357,283527225,614550654,6236408,484134891,24109055,192517470,1000000000,38852222,241076274,125636638,1000000000,158379143,183702750,616037175,46128788,106274785,234817582,233483446,26248562,37689241,408172760,1000000000,40980955,51279044,191503920,668656949,1000000000,298708075,482364604,432795646,31341676,68227232,173773491,66120316,1000000000,600110965,3662416,18702260,34471382,272324728,204931806,41374739,69689832,30881112,158979321,1000000000,6528057,140941685,371592193,460514306,728931125,52956634,392623697,209862191,730149655,537812929,688507827,37451015,502278980,1000000000,147532604,57156402,402720716,571422848,4479048,104710552,164981427,27568725,156311408,37786794,351527105,214681480,5066176,146944099,1000000000,41857265,83533858,1000000000,50855663,46447371,88463662,20470275,509175720,160632059,1000000000,53735493,121805339,92924908,828941962,172210402,62393160,389575462,206386507,388871069,196558251,29401440,433401362,1000000000,373158861,1000000000,297007486,31212726,81367368,360396198,34906323,94812491,491714897,26725438,88945247,5366574,924102880,35470662,29704075,217914197,167287889,500000900,268329481,1000000000,72303352,105510532,125286193,462246218,676850417,408460159,84476915,1000000000,10330792,175748195,37231042,237774311,86142214,500893623,364080337,1000000000,6495114,1000000000,342596728,206829193,21175521,601418916,581140504,91766454,64336620,299353911,1000000000,218176223,382793114,927716583,1000000000,481915269,148273301,152792566,221446661,435399152,93824830,98752776,1000000000,108804096,16071696,397260072,1000000000,83500730,419599231,1000000000,120101580,821882864,42210053,450237835,491522970,111068324,11336107,67413853,42879480,430219614,13435054,305294419,41769874,7962715,337164624,642318296,511498283,338371783,73325171,213907283,115046250,921474782,431256215,141033477,181944816,56520352,95047386,87546520,229999024,36556792,8419289,415577570,103076350,447524052,1000000000,56693680,143679410,83962598,49894853,36634650,47936886,151400656,811979543,513353200,1000000000,131889938,1000000000,175825038,114793431,436986710,128143818,7275793,134758798,299197846,33185737,213942734,764110211,14940860,395393538,3974759,29709706,632812012,168098536,635118307,111210969,32062395,15085853,187756536,21483246,9154649,17512887,130133442,154194582,807564286,190179036,68491479,17034447,1000000000,147643189,375101943,284274185,160582521,545441549,19248144,470085414,112620255,260738589,97291581,20129991,141356684,73608409,276578054,369459541,11970319,960918933,41175588,32508993,178288437,11645552,26877502,42275277,89680077,367536931,86142798,17962427,14238839,32651475,285153463,26409664,739909514,457424201,183854105,265200873,56509531,201202387,495616890,381297875,390843268,274851228,852651050,35346439,140925980,96236050,214814438,86077178,22523548,101074523,564259020,20922842,258795690,179541178,968261509,201557584,264580712,45082764,625054823,15647870,164736232,534199032,514861406,12144120,1000000000,13369347,491274908,61051499,160706642,130203399,80462759,34608537,18942933,1000000000,8512592,468477577,614019,1000000000,1827857,281787590,50555287,475669991,7090750,203952128,51297137,83530717,75038060,449825556,153587502,253818525,32493391,212560587,175190855,133871623,227665782,6155316,385457785,591762896,1000000000,284898744,568330688,125302965,46123235,87146612,63605574,322586240,236069544,543111915,76721506,745689035,1000000000,210089523,294475402,68642288,38613035,162714939,1000000000,282476350,1000000000,18983648,446463073,48546395,50302383,505325605,101312311,906919320,370228911,1000000000,306307862,1000000000,220777604,68055211,17748895,340664088,50238809,195961035,180594709,633012821,53920785,1000000000,409420925,144745132,194473658,11027561,1000000000,34013288,708960253,330881439,263086736,18174447,150829587,42836849,21043752,367926233,271327884,460870885,214346392,72650466,161406768,349191461,168728414,95545121,212433812,429092737,685465688,998335458,350150864,1000000000,338859744,1000000000,292030237,27960233,302067129,11626992,303196420,935898967,389491915,46341187,59666152,602246436,261454434,157292666,114722007,132261221,62854570,253598439,367286016,185603920,29893360,230963462,607307758,53965141,310738327,120790670,296086002,465619834,121952878,37785766,1000000000,1000000000,1000000000,390738207,320124199,334798098,75989123,7412312,43754443,39939594,3037035,854847741,43424905,165060810,572445601,112521095,1000000000,2225979,145032759,35793634,476006828,185794412,190012238,59335211,28819238,1000000000,324326524,31693888,531530744,186169761,42175805,375941860,96410129,171072996,23527980,204783787,1000000000,5589457,77095856,150341443,272438218,308193830,1875209,817885245,24075762,203982882,68528143,16861070,15706464,358624767,1000000000,22616379,40455278,630248,1000000000,10453008,683757250,114082590,1525117,1000000000,83510979,273471050,42698690,246125822,156220321,189624682,24097333,73555299,24055621,2511909,338954808,1000000000,30290289,79263302,366324747,330074824,88067923,75222094,134407406,192615717,356638230,19355856,52768254,188614032,45749816,14738910,26655830,316343165,330003562,1000000000,95176546,22385494,38651100,8977496,22993029,233369220,537315402,565462551,87948285,380091630,100785705,150651283,66857204,786166557,229199695,127400851,28792405,74811442,115750851,707949358,18473520,265558479,589789476,102641248,220631349,160599991,1000000000,280744179,1000000000,4194528,723866390,21163828,848622561,1000000000,105270,53371000,8606695,473563552,54625422,907984232,198293173,1000000000,182256894,10554080,628113197,94255615,28191294,265750733,51686542,559654700,48613092,498804966,380249909,117989026,369991171,182818907,25925127,185202994,854865222,345412926,32165124,23843543,291578811,1000000000,228816393,710869913,9625922,60761314,50742860,1000000000,694378,442276745,21616844,249395119,61850853,1000000000,16713759,5004016,27674477,933412150,246951167,9897035,1000000000,357593397,1000000000,291336055,40460828,69389854,206983158,275949527,401148282,572485652,120559935,222667794,17254217,4994490,313225401,1000000000,1000000000,203935148,1000000000,1000000000,202066874,2245164,435335768,62744743,654505544,179831335,335013388,257015584,0,957433681,339237334,154019136,592939422,80070009,161663534,342629137,556611751,62329079,109132735,1000000000,358246926,105405199,21799768,111958079,103571921,1000000000,41607732,103626485,81676143,84048810,969679949,101819648,579414292,167742252,1000000000,182172643,267410046,253700582,376806128,31424967,18789016,18672718,138113147,117330690,1000000000,330487182,65591784,783982453,30169149,48939970,1000000000,639781277,291600278,111832938,1000000000,189496378,1368699,648385883,432829477,294758430,185205724,163260454,282687883,910243631,782379,93874575,109942093,81070962,220819145,945282385,60091524,40712713,631309836,212773142,202739761,22427333,252253921,145206495,20586558,1000000000,564049269,46791651,1671529,126709847,199936094,1000000000,16934941,17061173,276622024,482991338,174820856,990595,27720379,257647515,50645066,267159899,1000000000,119259861,1000000000,122307389,381129757,234771492,46801292,176680124,165489661,73116453,796271105,77641257,70513826,77892114,38417213,218037764,252951790,18241146,523751365,1000000000,278830275,323981196,955862697,157973091,754749667,7393217,60842191,10189604,65398353,70705642,238609295,119661933,21812521,339261257,51477464,81825513,62949246,18284560,9849222,912191,1000000000,43853998,170996864,137110545,430647216,22258713,616027146,1000000000,82891179,29902329,1000000000,141590693,233261813,219052580,409841238,332354612,129393944,3961822,46561267,28207070,28586314,83397523,244205958,611002137,634816522,179214235,34508132,26453467,551998183,217473746,25574518,237944316,822360048,440312340,760305692,1000000000,57070527,268624576,132436361,51545762,2606256,289595843,357794033,14612166,116061887,145177962,233856449,48436630,96569392,143393667,211591213,71897388,22799934,1000000000,374697741,366369204,132989800,1000000000,119512214,1000000000,1000000000,470696780,144362794,9799640,162205889];